"""
Binary Tree 二叉树
    非线性数据结构
level 0:                             rootNode
level 1:               1node                         2node
level 2:      11node            12node       21node         22node
level 3: 111node   -    121node 122node       - -       221node 222node

Full Binary Tree        完全二叉树：没有空非叶子节点
Degenerate Binary Tree  退化二叉树：只有左节点/右节点
Skewed Binary Tree      倾斜二叉树：只有单个子节点/无子节点

Complete Binary Tree
Perfect Binary Tree
Balanced Binary Tree

Binary Search Tree
AVL Tree    # 左右节点高度差不超过1
"""


class NodeBST:
    def __init__(self,data):
        self.data = data
        self.right = None
        self.left = None


class BinaryTree:
    def __init__(self):
        self.root = None

    def isEmpty(self):
        if self.root is None:
            return True
        return False

    def setRoot(self,data):
        if self.root is None:
            self.root = NodeBST(data)
        else:
            self.root.data = data

    def PreOrderDFS(self):
        self._PreOrderDFS(self.root)

    def _PreOrderDFS(self, pos):
        """
        Pre-Order Depth-First Search
        前序深度优先遍历:Root-Left-Right
        """
        if pos is None:
            return "Empty Node!"
        print(pos.data,end = " ")
        self._PreOrderDFS(pos.left)
        self._PreOrderDFS(pos.right)

    def InOrderDFS(self):
        self._InOrderDFS(self.root)

    def _InOrderDFS(self, pos):
        """
        In-Order Depth-First Search
        中序深度优先遍历: Left-Root-Right
        """
        if pos is None:
            return "Empty Node!"
        self._InOrderDFS(pos.left)
        print(pos.data, end=" ")
        self._InOrderDFS(pos.right)

    def PostOrderDFS(self):
        self._PostOrderDFS(self.root)
    def _PostOrderDFS(self, pos):
        """
        Post-Order Depth-First Search
        后序深度优先遍历:Left-Right-Root
        """
        if pos is None:
            return "Empty Node!"
        self._PostOrderDFS(pos.left)
        self._PostOrderDFS(pos.right)
        print(pos.data, end=" ")

    def BFS(self):
        """
        Breadth-First-Search
        广度优先搜索遍历:Level Order Traversal
        """
        if self.root is None:
            return "Empty Node!"
        queue = [self.root] # 使用list实现Queue
        while queue:
            node = queue.pop(0)
            print(node.data,end = " ")
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    def _InsertNode(self, pos:NodeBST, data, Left:bool):
        """
        对指定节点执行插入值为data的节点，使用参数Left作为左右插入区分。
        Left为True时左插
        :param pos:
        :param data:
        :param Left:
        """
        if pos is None:
            return "Empty Node!"
        if Left is True and pos.left is None:
            pos.left = NodeBST(data)
        elif Left is True and pos.left is not None:
            # pos.left.target_list = target_list  # 非更改数据函数,应不插入
            return "Tree Branch Not Empty"
        elif Left is False and pos.right is None:
            pos.right = NodeBST(data)
        else:
            # pos.right.target_list = target_list # 非更改数据函数,应不插入
            return "Tree Branch Not Empty"

    def delNodeBFS(self,target):
        self._delNodeBFS(self.root,target)
        
    def _delNodeBFS(self,pos,target):
        """
        删除指定位置子节点。
        :param target:
        :return:
        """
        if pos is None:
            return "Empty Node!"
        queue = [pos] # 使用list实现Queue
        while queue:
            node = queue.pop(0)
            if target.data == node.left.data:
                node.left = None
                break
            if target.data == node.right.data:
                node.right = None
                break
            if target.left:
                queue.append(node.left)
            if target.right:
                queue.append(node.right)

    def _depth(self,pos):
        """
        求树深
        使用遍历/递归实现，此处使用递归
        :return:
        """
        if pos is None:
            return "Empty Node!"
        if pos.left is None and pos.right is None:
            return 1
        else:
            max(self._depth(pos.left)+1,self._depth(pos.right)+1)

    def depth(self):
        return self._depth(self.root)

    def _levelOfKey(self,key,pos,level):
        """
        找到指定 key 的层数 level
        使用循环进行
        :param key:
        :return:
        """
        if pos is None:
            return -1
        if pos.data == key:
            return level
        leftlevel = self._levelOfKey(key,pos.left,level+1)
        if leftlevel != -1:
            return leftlevel
        return self._levelOfKey(key,pos.right,level+1)


    def levelOfKey(self,key,pos):
        return self._levelOfKey(key,self.root)



"""        if pos is None:
            return "Node Is Empty, NO NEED To Delete!"
        elif pos.right is not None:
            pass
        elif pos.left is not None:
            pass
        else:
            pos = None
"""
testBinaryTree = BinaryTree()
testBinaryTree.root = NodeBST(1)
testBinaryTree.root.left = NodeBST(2)
testBinaryTree.root.right = NodeBST(3)
testBinaryTree.root.left.left = NodeBST(4)
testBinaryTree.root.left.right = NodeBST(0)
testBinaryTree.root.right.right = NodeBST(6)
"""
Now Binary Tree:
      1
  2      3
4   0  -   6
"""
print("InOrder Depth-First Search:", end=" ")
testBinaryTree.InOrderDFS()
print()

print("PreOrder Depth-First Search:", end=" ")
testBinaryTree.PreOrderDFS()
print()

print("PostOrder Depth-First Search:", end=" ")
testBinaryTree.PostOrderDFS()
print()

print("Breadth-First Search By Queue:", end=" ")
testBinaryTree.BFS()









class BinarySearchTree :
    """二叉搜索树"""
    def __init__(self):
        self.root = None

    def find(self, val):
        """查找方法，返回布尔值"""
        return self._find(self.root, val)

    def _find(self, node, val):
        if node is None:
            return False
        if node.val == val:
            return True
        if val < node.val:
            return self._find(node.left, val)
        else:
            return self._find(node.right, val)

    def insert(self, val):
        """插入方法，当前二叉搜索树定义为不包含重复key的树，所以当插入重复key时会失败"""
        if self.find(val):
            return False
        if not self.root:
            self.root = node = NodeBST(val)
        else:
            self._insert(self.root, val)
        return True

    def _insert(self, node, val):
        if not node:
            node = NodeBST(val)
        else:
            if val < node.val:
                node.left = self._insert(node.left, val)
            elif val > node.val:
                node.right = self._insert(node.right, val)
        return node

    def findmin(self):
        """查找key值最小的结点并返回该结点"""
        if not self.root:
            return None
        else:
            return self._findmin(self.root)

    def _findmin(self, node):
        if node.left:
            return self._findmin(node.left)
        else:
            return node

    def delete(self, val):
        """删除，返回布尔值"""
        if not self.find(val):
            return False
        else:
            self._delete(self.root, val)
            return True

    def _delete(self, node, val):
        """删除方法，最为复杂"""
        if not node:
            return None
        if val < node.val:
            node.left = self._delete(node.left, val)
        elif val > node.val:
            node.right = self._delete(node.right, val)
        else:
            # 当待删除结点有左右孩子时，选择左子树最大结点或者右子树最小节点用来替换该节点的值
            if node.left and node.right:
                node.val = self._findmin(node.right).val
                # 替换完成后把对应的左子树最大节点或者右子树最小节点进行递归删除
                node.right = self._delete(node.right, node.val)
            else:
                # 当待删除结点只有一个孩子时，直接用孩子替换该结点
                node = node.left if not node.right else node.right
        return node










